/*
 * =====================================================================================
 *
 *       Filename:  ListProblem.h
 *
 *    Description: 单链表经典问题解答
 *
 *        Version:  1.0
 *        Created:  2011-10-27 14:19:34
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  YOUR NAME (),
 *        Company:
 *
 * =====================================================================================
 */
#ifndef _ListProblem_H_
#define _ListProblem_H_

#include <iostream>
#include <functional>
#include <deque>

#include "Random.h"

//单链表节点信息，利用模板实现
template <class Comparable>
struct ListNode {
    ListNode(const Comparable &x, ListNode *n)
        : element(x), next(n) {
    }
    ListNode(void) {
        next = NULL;
    }

    Comparable element;
    ListNode   *next;
};

//创建节点个数为n的单链表
//节点的值为节点序号
//运行时间O(n)
template <class Comparable>
ListNode<Comparable> *createList(int n)
{
    if (n <= 0) {
        return NULL;
    }

    ListNode<Comparable> *head = new ListNode<int>(0, NULL);
    ListNode<Comparable> *p = head;

    for (int i = 1; i < n; ++i) {
        ListNode<Comparable> *node = new ListNode<int>(i, NULL);
        p->next = node;
        p = node;
    }

    return head;
}

//创建节点个数为n的单链表
//节点值随机
template <class Comparable>
ListNode<Comparable> *createRandList(int n)
{
    if (n <= 0) {
        return NULL;
    }

    srand(0);
    ListNode<Comparable> *head = new ListNode<Comparable>(averageRandom(-n, n), NULL);
    ListNode<Comparable> *p = head;

    for (int i = 1; i < n; ++i) {
        ListNode<Comparable> *node = new ListNode<Comparable>(averageRandom(-n, n), NULL);
        p->next = node;
        p = node;
    }

    return head;
}

//创建节点个数为n的单链表
//节点值也为n的链表
template <class Comparable>
ListNode<Comparable> *createSingleList(int n)
{
    if (n <= 0) {
        return NULL;
    }

    ListNode<Comparable> *head = new ListNode<Comparable>(n, NULL);
    ListNode<Comparable> *p = head;

    for (int i = 1; i < n; ++i) {
        ListNode<Comparable> *node = new ListNode<Comparable>(n, NULL);
        p->next = node;
        p = node;
    }

    return head;
}

//创建起始值为init，步进量为split，节点数为n的单链表
template <class Comparable>
ListNode<Comparable> *createList(int n, int init, int split)
{
    if (n <= 0) {
        return NULL;
    }

    ListNode<Comparable> *head = new ListNode<int>(init, NULL);
    ListNode<Comparable> *p = head;

    for (int i = 1; i < n; ++i) {
        ListNode<Comparable> *node = new ListNode<int>(init + i * split, NULL);
        p->next = node;
        p = node;
    }

    return head;
}

//创建节点个数为n的带环单链表
//节点的值为节点序号
//运行时间O(n)
template <class Comparable>
ListNode<Comparable> *createLoopList(long n)
{
    if (n <= 0) {
        return NULL;
    }

    ListNode<Comparable> *head = new ListNode<int>(0, NULL);
    ListNode<Comparable> *p = head;

    for (long i = 1; i < n; ++i) {
        ListNode<int> *node = new ListNode<int>(i, NULL);
        p->next = node;
        p = node;
    }

    p->next = head;
    return head;
}

//删除循环单链表
//循环删除头节点的下一个节点
//最后删除头节点
//运行时间O(n)
template <class Comparable>
void deleteList(ListNode<Comparable> *head)
{
    while (head && head->next) {
        if (head == head->next) {
            break;
        }

        ListNode<Comparable> *pd = head->next;
        head->next = head->next->next;
        delete pd;
        pd = NULL;
    }

    if (head) {
        delete head;
        head = NULL;
    }
}

//创建节点个数为n的带环单链表
//节点的值为节点序号
//环的入口节点为第entry节点，entry<=n
//运行时间O(n+entry)
template <class Comparable>
ListNode<Comparable> *createLoopList(int n, int entry)
{
    if (n <= 0) {
        return NULL;
    }

    ListNode<Comparable> *head = new ListNode<int>(0, NULL);
    ListNode<Comparable> *p = head;

    for (long i = 1; i < n; ++i) {
        ListNode<int> *node = new ListNode<int>(i, NULL);
        p->next = node;
        p = node;
    }

    ListNode<Comparable> *pentry = head;

    for (long i = 0; i < entry; ++i) {
        pentry = pentry->next;
    }

    p->next = pentry;
    return head;
}

//判断链表是否非递减
template <class Comparable>
bool isListGreatOrder(ListNode<Comparable> *head)
{
    while (head && head->next) {
        if (head->element > head->next->element) {
            return false;
        }

        head = head->next;
    }

    return true;
}

//计算链表节点个数
template <class Comparable>
int countList(ListNode<Comparable> *head)
{
    int cnt = 0;

    while (head) {
        cnt++;
        head = head->next;
    }

    return cnt;
}

//在单链表中查找节点
template <class Comparable>
ListNode<Comparable> *findListElement(ListNode<Comparable> *head, const Comparable &x)
{
    while (head) {
        if (head->element == x) {
            break;
        }

        head = head->next;
    }

    return head;
}

//判断有序链表是否有重复元素
template <class Comparable>
bool isHaveDupKeys(ListNode<Comparable> *head)
{
    if (head == NULL || head->next == NULL) {
        return false;
    }

    ListNode<Comparable> node;
    node.next = head;
    ListNode<Comparable> *pre = node.next;
    ListNode<Comparable> *cur = pre->next;

    while (cur) {
        if (pre->element == cur->element) {
            return true;
        }

        pre = cur;
        cur = cur->next;
    }

    return false;
}

//删除带环单链表
//先删除入口节点之前的节点
//然后循环删除入口节点后面的节点
//最后删除入口节点
//运行时间O(n)
template <class Comparable>
void deleteList(ListNode<Comparable> *head, ListNode<Comparable> *pentry)
{
    if (pentry == NULL) {
        return deleteList(head);
    }

    while (head && head != pentry) {
        ListNode<Comparable> *pd = head;
        head = head->next;
        delete pd;
        pd = NULL;
    }

    while (pentry && pentry->next) {
        if (pentry == pentry->next) {
            break;
        }

        ListNode<Comparable> *pd = pentry->next;
        pentry->next = pentry->next->next;
        delete pd;
        pd = NULL;
    }

    if (pentry) {
        delete pentry;
        pentry = NULL;
    }
}

//打印单链表
template <class Comparable>
void printList(ListNode<Comparable> *head)
{
    while (head) {
        std::cout << head->element << " ";
        head = head->next;
    }

    std::cout << std::endl;
}

//问题1：如何判断一个单项链表是否存在环？
//设置两个指针(slow, fast)，初始值都指向头
//slow每次前进一步，fast每次前进二步
//如果链表存在环，则fast先进入环， slow后进入环
//两个指针在环中走动，必定相遇。
template <class Comparable>
bool isListLoop(ListNode<Comparable> *head)
{
    if (head == NULL) {
        return false;
    }

    ListNode<Comparable> *slow = head;
    ListNode<Comparable> *fast = head;

    while (fast && fast->next) {//到达结尾退出循环
        slow = slow->next;
        fast = fast->next->next;

        if (fast == slow) {
            break;//相遇退出循环
        }
    }

    //未到达结尾，则存在环
    return !((fast == NULL) || (fast->next == NULL));
}

//问题2：如何知道环的长度？
//提问1：是否确定有环？如果确定有环，代码会简洁很多
//现假设肯定有环
//设置两个指针(slow, fast)，初始值都指向头
//slow每次前进一步，fast每次前进二步
//如果链表存在环，则fast先进入环， slow后进入环
//两个指针在环中第一次相遇后，到第二次相遇时
//走过的距离便是环的长度
//如果有环，返回环的长度，否则返回0
template <class Comparable>
int loopLenListLoop(ListNode<Comparable> *head)
{
    if (head == NULL) {
        return 0;
    }

    ListNode<Comparable> *slow = head;
    ListNode<Comparable> *fast = head;

    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;

        if (fast == slow) {
            break;
        }
    }

    int len = 0;

    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        len++;

        if (fast == slow) {
            break;
        }
    }

    return len;
}

//问题3：已知一个单向链表存在环，如果找出该环的入口点？
//设置两个指针(slow, fast)，初始值都指向头
//slow每次前进一步，fast每次前进二步
//如果链表存在环，则fast先进入环， slow后进入环
//从两指针第一次相遇点开始算起
//令p1指向链表头，p2指向相遇点
//p1与p2相遇点即为该环的入口点
template <class Comparable>
ListNode<Comparable> *entryLoopList(ListNode<Comparable> *head)
{
    if (head == NULL) {
        return 0;
    }

    ListNode<Comparable> *slow = head;
    ListNode<Comparable> *fast = head;
    ListNode<Comparable> *p1 = head;

    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;

        if (fast == slow) {
            break;
        }
    }

    while (p1 != slow) {
        p1 = p1->next;
        slow = slow->next;
    }

    return p1;
}

//删除带环列表
template <class Comparable>
void deleteLoopList(ListNode<Comparable> *head)
{
    deleteList(head, entryLoopList(head));
}

//问题4：带环链表的长度是多少？
//带环链表的长度为起点到环入口的长度加上环的长度
//仔细参考问题2和问题3
template <class Comparable>
int lenListLoop(ListNode<Comparable> *head)
{
    if (head == NULL) {
        return 0;
    }

    ListNode<Comparable> *slow = head;
    ListNode<Comparable> *fast = head;

    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;

        if (slow == fast) {
            break;
        }
    }

    ListNode<Comparable> *p1 = head;
    int len = 0;

    while (p1 != fast) {
        p1 = p1->next;
        fast = fast->next;
        len++;
    }

    fast = slow;

    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        len++;

        if (slow == fast) {
            break;
        }
    }

    return len;
}

//题5：判断两个链表是否相交
//首先判断两个头节点是否相交
//先遍历一个链表，得到最后节点end1
//然后将end1链接到另一个链表
//遍历另一个链表
//如果回到开始节点，则相交
//如果不能回到开始节点，则不相交
//最后还原节点end1
template <class Comparable>
bool isTwoListCross(ListNode<Comparable>* head1, ListNode<Comparable>* head2)
{
    assert(head1 && head2);

    //头结点是否相交
    if (head1 == head2) {
        return true;
    }

    ListNode<Comparable> *end1 = head1;

    while (end1 && end1->next) {
        end1 = end1->next;
    }

    //将最后节点连接到另一链表
    end1->next = head2;

    ListNode<Comparable>* p2 = head2;

    while (p2 && p2->next) {
        p2 = p2->next;

        if (p2 == head2) {
            break;
        }
    }

    //还原节点
    end1->next = NULL;

    //返回是否相交
    return (p2 && p2->next);
}

//问题6：已知两个链表（没有环）相交，如何找出相交的第一个节点？
//将其中一条链表链接形成循环链表
//于是问题转化为求带环链表的入口节点
//求出带环链表的入口节点
//还原链表
//扩展问题：如果可能有环呢？
template <class Comparable>
ListNode<Comparable> *crossOfTwoList(ListNode<Comparable> *head1, ListNode<Comparable> *head2)
{
    //查找最后节点
    ListNode<Comparable> *end1 = head1;

    while (end1 && end1->next) {
        end1 = end1->next;
    }

    //连接另一链表，形成带环链表
    end1->next = head1;

    //求出带环链表的入口节点
    ListNode<Comparable> *pentry = entryLoopList(head2);

    //还原链表
    end1->next = NULL;

    return pentry;
}

//问题7：如何对一个单向链表进行反转？
//用三个指针操作
//仔细检查边界条件
//头节点后面没有节点
//返回新的头节点
template <class Comparable>
ListNode<Comparable> *reverseList(ListNode<Comparable> *head)
{
    if (head == NULL || head->next == NULL) {
        return head;
    }

    ListNode<Comparable> *pre = NULL;
    ListNode<Comparable> *cur = head;
    ListNode<Comparable> *nex = NULL;

    while (cur && cur->next) {
        nex = cur->next;
        cur->next = pre;
        pre = cur;
        cur = nex;
    }

    cur->next = pre;
    return cur;
}

//问题7的递归实现，需要深入理解递归！
template <class Comparable>
ListNode<Comparable> *_reverseList2(ListNode<Comparable> *head)
{
    if (head->next == NULL) {
        return head;
    }

    ListNode<Comparable> *rhead = _reverseList2(head->next);
    head->next->next = head;
    head->next = NULL;
    return rhead;
}

template <class Comparable>
ListNode<Comparable> *reverseList2(ListNode<Comparable> *head)
{
    //处理没有或者只有一个节点的情况
    if (head == NULL && head->next == NULL) {
        return head;
    }

    return _reverseList2(head->next);
}

//问题8：已知一个单向链表，不知道该链表的头指针
//已知一个节点的指针，如何将该节点从链表中删除？
//将该节点p之后的节点p->next的数据拷贝到节点p
//更改连接
//然后删除p之后的节点
template <class Comparable>
void deleteListNode(ListNode<Comparable> *pNode)
{
    assert(pNode && pNode->next);
    pNode->element = pNode->next->element;
    pNode->next = pNode->next->next;
    delete pNode;
    pNode = NULL;
}

//问题9：已知一个单向链表，不知道该链表的头指针
//已知一个节点的指针， 如何在该节点前面插入一个结点？
//将节点p的拷贝到新节点中
//将新节点连接到节点p之后
//将新节点的数据拷贝到p中
template <class Comparable>
void insertListNode(ListNode<Comparable> *pNode, ListNode<Comparable> *nNode)
{
    assert(pNode && nNode);
    Comparable x = pNode->element;
    nNode->next = pNode->next;
    pNode->next = nNode;
    pNode->element = x;
}

//问题10：找出单链表中倒数第K个结点。
//设置两个指针(p1, p2)，初始都指向头节点
//p1指向第K个节点
//p2指向头节点
//然后同时走，p1结束后，p2便指向倒数第K个节点
template <class Comparable>
ListNode<Comparable> *findReversalKnode(ListNode<Comparable> *head, int k)
{
    ListNode<Comparable> *p1 = head;
    ListNode<Comparable> *p2 = head;

    for (int i = 0; i < k - 1; ++i) {
        p1 = p1->next;
    }

    while (p1->next) {
        p1 = p1->next;
        p2 = p2->next;
    }

    return p2;
}

//问题11：找出单链表的中间节点
//设置两个指针(slow, fast)，初始都指向头节点
//slow一次走一步，fast一次走两步
//当fast走到结尾时，slow便指向中间节点
template <class Comparable>
ListNode<Comparable> *findMidNode(ListNode<Comparable> *head)
{
    ListNode<Comparable> *slow = head;
    ListNode<Comparable> *fast = head;

    while (fast && fast->next && fast->next->next) {
        slow = slow->next;
        fast = fast->next->next;
    }

    return slow;
}

//问题12：有个二级单链表，其中每个元素都含有一个指向一个单链表的指针
template <class Comparable>
struct twoListNode {
    Comparable  element;
    twoListNode *next; //下一个元素
    twoListNode *head; //另一个单链表
};//注：都是无环的
//写程序把这个二级链表展开称一级单链表:
//例如: "v" represent "head", ">" represent "next"
//
// 1>2>3>NULL
// v
// 4>5>6>NULL
// v
// 7>8>9>NULL
// v
// NULL
//
//展开以后是 1>2>3>4>5>6>7>8>9>NULL
template <class Comparable>
twoListNode<Comparable>* expandTwoListToSingle(twoListNode<Comparable> *head)
{
    while (head) {
        //连接二级单链表
        twoListNode<Comparable> *end = head;

        while (end->next) {
            end = end->next;
        }

        end->next = head->head;

        //去掉二级单链表
        end = head;
        head = head->head;
        end->head = NULL;
    }
}

//问题13：给定一种链表，里面每个节点里都有一个0-9的数字，用来表示一个超大数，请设计程序做两个链表的加法运算。
//比如：9>9>9>NULL + 1>NULL => 1>0>0>0>NULL
//因为存在进位+1问题，而单链表永远指向前
//使用递归可以解决进位问题
//M代表链表1的位数，N代表链表2的位数
template <class Comparable>
int addImpWithList(ListNode<Comparable> *head1, int M,
                   ListNode<Comparable> *head2, int N,
                   ListNode<Comparable> *&newHead)
{
    if (head1 == NULL) {
        return 0;
    }

    newHead = new ListNode<Comparable>(0, NULL);

    if (M > N) {
        int result = addImpWithList(head1->next, M - 1, head2, N, newHead->next);
        newHead->element = head1->element + result;
    } else {//M==N
        int result = addImpWithList(head1->next, M - 1, head2->next, N - 1, newHead->next);
        newHead->element = head1->element + head2->element + result;
    }

    if (newHead->element >= 10) {
        newHead->element -= 10;
        return 1;
    } else {
        return 0;
    }
}

//问题15：两个有序链表合并。
//有两个有序链表，各自内部是有序的，但是两个链表之间是无序的
//写一个Merge函数
//如果两个有序链表交叉呢？
//根据合并排序的思想修改指针即可
template <class Comparable, class Comparator>
ListNode<Comparable> *merageList(
    ListNode<Comparable> *head1,
    ListNode<Comparable> *head2,
    Comparator lessthan)
{
    if (head1 == NULL) {
        return head2;
    }

    if (head2 == NULL) {
        return head1;
    }

    ListNode<Comparable> *p = NULL;

    if (lessthan(head1->element, head2->element)) {
        p = head1;
        head1 = head1->next;
    } else {
        p = head2;
        head2 = head2->next;
    }

    ListNode<Comparable> *head = p;

    while (head1 && head2) {
        if (lessthan(head1->element, head2->element)) {
            p->next = head1;
            head1 = head1->next;
        } else {
            p->next = head2;
            head2 = head2->next;
        }

        p = p->next;
    }

    if (head1) {
        p->next = head1;
    } else if (head2) {
        p->next = head2;
    } else {
        p->next = NULL;
    }

    return head;
}

//问题15扩展：两个有序相交链表合并。
//有两个有序链表，各自内部是有序的，但是两个链表之间是无序的
//写一个Merge函数
template <class Comparable, class Comparator>
ListNode<Comparable> *merageCrossList(
    ListNode<Comparable> *head1,
    ListNode<Comparable> *head2,
    Comparator lessthan)
{
    if (head1 == NULL) {
        return head2;
    }

    if (head2 == NULL) {
        return head1;
    }

    //判断一开始就相交的情形
    if (head1 == head2) {
        return head1;
    }

    ListNode<Comparable> *p = NULL;

    if (lessthan(head1->element, head2->element)) {
        p = head1;
        head1 = head1->next;
    } else {
        p = head2;
        head2 = head2->next;
    }

    ListNode<Comparable> *head = p;

    while (head1 && head2) {
        //判断相交
        if (head1 == head2) {
            break;
        }

        if (lessthan(head1->element, head2->element)) {
            p->next = head1;
            head1 = head1->next;
        } else {
            p->next = head2;
            head2 = head2->next;
        }

        p = p->next;
    }

    if (head1) {
        p->next = head1;
    } else if (head2) {
        p->next = head2;
    } else {
        p->next = NULL;
    }

    return head;
}

//题16：对于两个有序无环单链表，求这两个链表的交集
//比如：1>2>3>4>NULL 交 2>4>5>NULL => 2>4>NULL
template <class Comparable>
ListNode<Comparable> *intersectionOfTwoOrderedList(
    ListNode<Comparable> *head1, ListNode<Comparable> *head2)
{
    if (head1 == NULL || head2 == NULL) {
        return NULL;
    }

    ListNode<Comparable> *head = new ListNode<Comparable>();
    ListNode<Comparable> *p = head;

    while (head1 && head2) {
        if (head1->element < head2->element) {
            head1 = head1->next;
        } else if (head1->element > head2->element) {
            head2 = head2->next;
        } else {
            p->next = new ListNode<Comparable>(head1->element, NULL);
            head1 = head1->next;
            head2 = head2->next;
            p = p->next;
        }
    }

    ListNode<Comparable> *pd = head;
    head = head->next;
    delete pd;
    pd = NULL;
    return head;
}

//题17：单链表排序
//选择排序、插入排序、冒泡排序、快速排序、归并排序
/////////////////////////////////////////////////////////////////////
//单链表冒泡排序
template <class Comparable>
ListNode<Comparable> *bubbleSortList(ListNode<Comparable> *head)
{
    //处理没有节点和只有一个节点
    if (head == NULL || head->next == NULL) {
        return head;
    }

    //现在单链表中至少有两个节点
    //我们增加一个节点，放在第一个节点的前面
    //主要是为了便于比较，如果第一个节点没有前驱，我们不能交换地址
    //能很大程度上降低书写的程序复杂度
    ListNode<Comparable> node;
    node.next = head;
    ListNode<Comparable> *cur = NULL;
    ListNode<Comparable> *nex = NULL;
    ListNode<Comparable> *pre = NULL;
    ListNode<Comparable> *end = NULL;

    //从右到左扫描
    for (end = NULL; end != node.next; end = cur) {
        //从左到右扫描
        for (pre = &node, cur = node.next; cur->next != end; cur = cur->next) {
            nex = cur->next;

            if (cur->element > nex->element) {
                pre->next = cur->next;
                cur->next = nex->next;
                nex->next = cur;
                cur = nex;
            }

            pre = cur;
        }
    }

    return node.next;
}

//单链表选择排序
template <class Comparable>
ListNode<Comparable> *selectSortList(ListNode<Comparable> *head)
{
    //处理没有节点和只有一个节点
    if (head == NULL || head->next == NULL) {
        return head;
    }

    //现在单链表中至少有两个节点
    //我们增加一个节点，放在第一个节点的前面
    //主要是为了便于比较，如果第一个节点没有前驱，我们不能交换地址
    //能很大程度上降低书写的程序复杂度
    ListNode<Comparable> node;
    node.next = head;
    ListNode<Comparable> *newHead = NULL;

    while (node.next != NULL) {
        //这里找出最大的值，如果找出最小值，最后的插入操作非常困难
        //编程复杂度非常高
        ListNode<Comparable> *max = node.next;
        ListNode<Comparable> *maxPre = &node;
        ListNode<Comparable> *cur = max->next;
        ListNode<Comparable> *pre = max;

        while (cur != NULL) {
            if (max->element < cur->element) {
                max = cur;
                maxPre = pre;
            }

            pre = cur;
            cur = cur->next;
        }

        maxPre->next = max->next;
        max->next = newHead;
        newHead = max;
    }

    return newHead;
}

//单链表插入排序
template <class Comparable>
ListNode<Comparable> *insertSortList(ListNode<Comparable> *head)
{
    //处理没有节点和只有一个节点
    if (head == NULL || head->next == NULL) {
        return head;
    }

    //现在单链表中至少有两个节点
    //我们增加一个节点，放在第一个节点的前面
    //主要是为了便于比较，如果第一个节点没有前驱，我们不能交换地址
    //能很大程度上降低书写的程序复杂度
    ListNode<Comparable> node;
    node.next = head;
    ListNode<Comparable> out;

    while (node.next != NULL) {
        //先取下节点
        ListNode<Comparable> *tmp = node.next;
        node.next = node.next->next;

        //找出恰当位置
        ListNode<Comparable> *cur = out.next;
        ListNode<Comparable> *pre = &out;

        while (cur != NULL) {
            if (tmp->element < cur->element) {
                break;
            }

            pre = cur;
            cur = cur->next;
        }

        //连接到输出列表
        pre->next = tmp;
        tmp->next = cur;
    }

    return out.next;
}

//单链表快速排序，分而治之，交换指针，不好理解
template <class Comparable>
ListNode<Comparable> *_quickSortList(ListNode<Comparable> *pivot, ListNode<Comparable> *pivotNext)
{
    if (pivot == NULL) {
        return pivotNext;
    }

    ListNode<Comparable> left;
    ListNode<Comparable> right;

    ListNode<Comparable> *left_walk = &left;
    ListNode<Comparable> *right_walk = &right;

    for (ListNode<Comparable> *cur = pivot->next; cur != NULL; cur = cur->next) {
        if (cur->element < pivot->element) {
            left_walk->next = cur;
            left_walk = cur;
        } else {
            right_walk->next = cur;
            right_walk = cur;
        }
    }

    left_walk->next = right_walk->next = NULL;
    pivot->next = _quickSortList(right.next, pivotNext);
    return _quickSortList(left.next, pivot);
}
template <class Comparable>
ListNode<Comparable> *quickSortList(ListNode<Comparable> *head)
{
    ListNode<Comparable> *end = NULL;
    return _quickSortList(head, end);
}

//归并操作，两个链表必须有序
template <class Comparable>
ListNode<Comparable> *mergeList(ListNode<Comparable> *head1, ListNode<Comparable> *head2)
{
    if (head1 == NULL) {
        return head2;
    }

    if (head2 == NULL) {
        return head1;
    }

    ListNode<Comparable> head;
    ListNode<Comparable> *cur = &head;

    while (head1 && head2) {
        if (head1->element < head2->element) {
            cur->next = head1;
            head1 = head1->next;
        } else {
            cur->next = head2;
            head2 = head2->next;
        }

        cur = cur->next;
    }

    cur->next = (head1 == NULL) ? head2 : head1;
    return head.next;
}

//单链表归并排序，自顶向下，分而治之，交换指针
template <class Comparable>
ListNode<Comparable> *mergeSortList(ListNode<Comparable> *head)
{
    if (head == NULL || head->next == NULL) {
        return head;
    }

    ListNode<Comparable> *slow = head;
    ListNode<Comparable> *fast = head->next; //注意这里！当节点数为2时，fast = head是不正确的

    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }

    fast = slow->next;
    slow->next = NULL;
    return mergeList(mergeSortList(head), mergeSortList(fast));
}

//单链表归并操作，自底向上，分而治之，交换指针
//无递归调用，效率高（队列实现）
template <class Comparable>
ListNode<Comparable> *mergeSortListBU(ListNode<Comparable> *head)
{
    if (head == NULL || head->next == NULL) {
        return head;
    }

    std::deque<ListNode<Comparable> *> d;
    ListNode<Comparable> *t = NULL;

    for (ListNode<Comparable> *cur = head; cur != NULL;) {
        t = cur;
        cur = cur->next;
        t->next = NULL;
        d.push_back(t);
    }

    t = d.front();
    d.pop_front();

    while (!d.empty()) {
        d.push_back(t);
        ListNode<Comparable> *head1 = d.front();
        d.pop_front();
        ListNode<Comparable> *head2 = d.front();
        d.pop_front();
        t = mergeList(head1, head2);
    }

    return t;
}
/////////////////////////////////////////////////////////////////////

//题18：删除单链表中重复的元素
//如果可以使用散列表，用散列表
//如果不能，则双重遍历，运行时间O(n^2)
template <class Comparable>
ListNode<Comparable> *deleteDupKeys(ListNode<Comparable> *head)
{
    if (head == NULL || head->next == NULL) {
        return head;
    }

    ListNode<Comparable> node;
    node.next = head;
    ListNode<Comparable> *cur = node.next->next;

    while (cur) {
        ListNode<Comparable> *preCheck = &node;
        ListNode<Comparable> *check = node.next;

        while (check != cur) {
            if (check->element == cur->element) {
                ListNode<Comparable> *t = check;
                preCheck->next = check->next;
                check = check->next;
                delete t;
                break;
            }

            preCheck = check;
            check = check->next;
        }

        cur = cur->next;
    }

    return node.next;
}

//解法二：利用先排序，再删除，运行时间O(nlgn)
template <class Comparable>
ListNode<Comparable> *deleteDupKeysUseSort(ListNode<Comparable> *head)
{
    if (head == NULL || head->next == NULL) {
        return head;
    }

    head = quickSortList(head);
    ListNode<Comparable> node;
    node.next = head;
    ListNode<Comparable> *preCheck = node.next;
    ListNode<Comparable> *check = node.next->next;

    while (check != NULL) {
        if (preCheck->element == check->element) {
            ListNode<Comparable> *t = check;
            preCheck->next = check->next;
            check = check->next;
            delete t;
            continue;
        }

        preCheck = check;
        check = check->next;
    }

    return node.next;
}

//题19：单链表交换任意两个元素（不包括表头）
template <class Comparable>
void swapListPointer(ListNode<Comparable> *pre1, ListNode<Comparable> *pre2)
{
    if (pre1 == NULL || pre1->next == NULL || pre2 == NULL || pre2->next == NULL) {
        return ;
    }

    ListNode<Comparable> *cur1 = pre1->next;
    ListNode<Comparable> *cur2 = pre2->next;

    if (cur1 == pre2) {
        pre1->next = cur2;
        cur1->next = cur2->next;
        cur2->next = cur1;
    } else {
        pre1->next = cur2;
        pre2->next = cur1;
        ListNode<Comparable> *t = cur1->next;
        cur1->next = cur2->next;
        cur2->next = t;
    }
}
#endif
